// ========================================================
// DIFFICULT TEST PROGRAM: RECURSIVE FIBONACCI
//
// Calculates:
//
//     Fibonacci(7) = 13
//
// Fibonacci sequence:
//
//     0, 1, 1, 2, 3, 5, 8, 13
//
// THIS PROGRAM DEMONSTRATES:
//
//   1. Recursive function calls.
//   2. Calling a function with JAL.
//   3. Returning from a function with JALR.
//   4. Using x1 as the return-address register.
//   5. Using x2 as a stack pointer.
//   6. Creating and removing stack frames.
//   7. Saving return addresses on the stack.
//   8. Saving function arguments on the stack.
//   9. Saving intermediate results on the stack.
//  10. Loading and storing 32-bit values with LW and SW.
//  11. Using a recursive base case.
//  12. Combining the results of two recursive calls.
//  13. Using positive and negative immediate values.
//  14. Using BLT for a conditional decision.
//  15. Maintaining separate data for nested function calls.
//
// REGISTER USE:
//
//   x1  = return address
//   x2  = stack pointer
//   x5  = first recursive result
//   x6  = comparison value 2
//   x10 = function argument n
//   x12 = returned Fibonacci value
//
// STACK FRAME:
//
//   0(x2) = result of Fibonacci(n - 1)
//   4(x2) = saved value of n
//   8(x2) = saved return address
//
// EXPECTED OUTPUT:
//
//   Fibonacci(7) = 13
//
// IMPORTANT:
//
//   This example assumes that memory beginning below address
//   1024 is available for use as the program stack.
// ========================================================


// --------------------------------------------------------
// Main program
// --------------------------------------------------------


start:

        addi  x2, x0, 1024         // Initialize stack pointer
        addi  x10, x0, 7           // Calculate Fibonacci(7)

        jal   x1, Fibonacci         // Call recursive function

        cout  << "Fibonacci(7) = " << x12 << endl

        jal   x0, EndProgram        // Skip function code


// --------------------------------------------------------
// Fibonacci
//
// Input:
//
//   x10 = n
//
// Output:
//
//   x12 = Fibonacci(n)
//
// Formula:
//
//   Fibonacci(0) = 0
//   Fibonacci(1) = 1
//
//   Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
// --------------------------------------------------------

Fibonacci:
        addi  x2, x2, -12           // Create 12-byte stack frame

        sw    x1, 8(x2)             // Save return address
        sw    x10, 4(x2)            // Save original n

        addi  x6, x0, 2             // Base-case comparison value
        blt   x10, x6, FibonacciBase


// --------------------------------------------------------
// Calculate Fibonacci(n - 1)
// --------------------------------------------------------

        addi  x10, x10, -1          // Argument = n - 1
        jal   x1, Fibonacci          // Recursive call

        sw    x12, 0(x2)             // Save Fibonacci(n - 1)


// --------------------------------------------------------
// Calculate Fibonacci(n - 2)
// --------------------------------------------------------

        lw    x10, 4(x2)             // Restore original n
        addi  x10, x10, -2           // Argument = n - 2

        jal   x1, Fibonacci          // Recursive call

        lw    x5, 0(x2)              // Load Fibonacci(n - 1)
        add   x12, x5, x12           // Add the two results

        jal   x0, FibonacciReturn


// --------------------------------------------------------
// Base case
//
// If n is 0 or 1, Fibonacci(n) equals n.
// --------------------------------------------------------

FibonacciBase:
        add   x12, x10, x0           // Return n


// --------------------------------------------------------
// Remove stack frame and return
// --------------------------------------------------------

FibonacciReturn:
        lw    x1, 8(x2)              // Restore return address
        addi  x2, x2, 12             // Remove stack frame

        jalr  x0, 0(x1)              // Return to caller


EndProgram:
